1. Technical Field
This invention generally relates to graphical shape data. More specifically, this invention relates to partitioning and load balancing graphical shape data for parallel applications.
2. Background Art
When semiconductor chips are created, there are certain patterns or shapes formed on a semiconductor wafer. These patterns are placed in many different layers. After all of the patterns for all of the layers are made, the semiconductor chip is complete, other than external wiring and packaging.
Often, a graphics file is used to store all of this pattern and shape information. Originally, the process of creating a graphics file was tedious, as each shape was physically laid out on a grid. Since then, these types of systems have become much more automated. Currently, designers use design tools that xe2x80x9chidexe2x80x9d the actual graphical layout of the semiconductor chip. Instead, the designers use representations of individual or large parts, and the design tools then know how to actually layout the different parts. Once the design of the chip is complete, the design tools can output the graphics file. A semiconductor processing facility then uses the graphics file to create the semiconductor chip.
One common graphics file for semiconductor chips is called a xe2x80x9cGL/1xe2x80x9d graphics file, which is a particular file format that represents the graphical shape data for the chip. As is known in the art, a GL/1 graphics file contains a number of cells, which can range into the tens of thousands. Each cell has a number of xe2x80x9ctransformsxe2x80x9d, which can take a different cell and perform various functions on it (such as rotating it, mirroring it, arraying it, etc.). To one skilled in the art of computer science, the transforms act like xe2x80x9cincludesxe2x80x9d in the sense that other cells are included in the current cell. Unlike software, however, the transforms can manipulate the included cells in physical terms. In GL/1 files, there is a xe2x80x9cprimexe2x80x9d cell which is essentially the master cell. There are also xe2x80x9cleafxe2x80x9d or xe2x80x9cbasexe2x80x9d cells where the transform will be xe2x80x9cnullxe2x80x9d, meaning that this cell does not include another cell. The base cells will be the building blocks that other cells can use. As such, these graphics files are nested and hierarchical because many cells may use the base cells and because some cells will include additional cells which themselves include additional cells, etc., until the base cells are finally included.
The cell structure of a GL/1 graphics file may be thought of as a tree: the prime cell is the root of the tree; the leaf or base cells are the leaves of the tree; and the cells between the prime cell and the base cells are the branches. It should also be noted that each cell is part of a level and the GL/1 graphics file will contain all of these levels. Because of this, when the GL/1 graphics file is examined through tools that allow the graphical shape data to be seen, a representation of the graphical shape data will be three dimensional.
Prior to manufacturing the semiconductor chip, the semiconductor processing fab generally runs checks and pre-manufacturing applications and processing on the graphics file. For instance, the facility might run xe2x80x9cfillxe2x80x9d functions that add metal shapes at levels for the optimum metal-to-oxide ratio to improve manufacturing yields. Alternatively, they could run a xe2x80x9ccheesexe2x80x9d function that removes metal to create the same optimum ratio. Additionally, the facility might run a very important xe2x80x9cdesign rule checkingxe2x80x9d (DRC) function that checks to ensure that the patterns and shapes meet manufacturing design rules. If some of these design rules are not met, the chip may not function correctly or may have poor manufacturing yield.
The graphics files are beginning to create problems for semiconductor processing facilities. Without a method and apparatus for solving these problems, semiconductor processing facilities will be hampered more and more by these problems and need to invest in additional facilities improvements.
Before proceeding with a summary of the invention, it is beneficial to more particularly discuss the problems associated with graphics files. A major problem associated with these files is the amount of data needed for their representation. Contemporary graphics files can be as large as 3 gigabytes. In the future, even larger files will be prevalent. One common graphics file format is called xe2x80x9cGL/1xe2x80x9d. This format contains all of the many levels and interconnects of the semiconductor chip. Current GL/1 processing tools allow single levels of GL/1 to be separated. However, to perform this function, these tools require the entire graphics file to be loaded into computer memory so that the tools can remove the particular level. It will continue to become much harder to use computer systems with the necessary memory capable of removing the levels. Moreover, as semiconductor technology increases, the number and complexity of the levels increases. Even if the levels can be separated from the graphics file, some of the levels are so complex that it takes lengthy computation time to process these complex levels. These requirements are only going to increase in a super-linear or exponential fashion.
Thus, without a way to partition and load balance graphical shape data for parallel applications, semiconductor processing facilities are going to continue to outlay capital expenditures for increasingly powerful computers having substantial amounts of memory or are going to simply reach a time when their most powerful computers cannot process the graphics files.
The preferred embodiments of the present invention solve these problems by splitting the large graphics file into smaller output xe2x80x9cframesxe2x80x9d of graphics files. The splitting process is load balanced amongst any number of processors. This allows many processors to be used in parallel to divide the large graphics file and to then process the resulting smaller frames. Additionally, the load balancing is performed in such a manner that only portions of the graphics file are loaded by any one processor. This reduces memory and computational requirements for any one processor. Preferably, the graphics file is divided in a three-dimensional manner, such that any one processor will be assigned one three-dimensional block or volume of the graphics file. The three-dimensional partition of the graphics file will become one frame, and the one processor accesses the graphics file to copy its three-dimensional partition into the new output frame. Applications, such as various check tools, may be used on each computer to process the graphics file. This divides application processing amongst the processors.
Preferably, a metric of xe2x80x9cdata densityxe2x80x9d is used to divide the graphics file. The xe2x80x9cdata densityxe2x80x9d metric is the ratio of graphics file data per three-dimensional block or volume of space. The data density could have units of, for instance, bytes per cubic millimeter. The data density metric is used to evaluate and divide the graphics files.
The foregoing and other features and advantages of the present invention will be apparent in the preferred embodiments of the invention, as illustrated in the accompanying drawings.